package List.SequenceList;

import java.util.Arrays;

/**
 * 顺序表
 * @param <T>
 */
public class SequenceList<T>{
    private int N=0;   //记录当前顺序表中的元素个数
    private T[] eles;  //顺序表用数组实现，存储元素

    //构造方法,初始化数组和长度
    public SequenceList(int capacity){
        this.eles = (T[])new Object[capacity];
        this.N = 0;
    }

    //清空线性表
    public void clear(){
        this.N= 0;
    }

    //判断是否为空表
    public boolean isEmpty(){
        return this.N==0;
    }

    //获取线性表的长度
    public int length(){
        return this.N;
    }

    //获取指定位置的元素
    public T get(int i){
        return eles[i];
    }

    //添加元素
    public void insert(T t){
        if(N==eles.length){
            eles = reSize(2*eles.length);
        }
        eles[N++] = t;
    }

    //在位置i处插入元素t
    public void insert(int i,T t){
        //插入元素前要进行是否扩容的判断
        if(N == eles.length){
            eles = reSize(2*eles.length);
        }
        N++;  //元素个数+1
        for (int j = N; j > i ; j--) {  //将i以及i之后的元素依次向后推移一位
            eles[j-1]= eles[j-2];
        }
        eles[i] = t;
    }

    //删除指定位置i处的元素，并返回该元素
    public T remove(int i){
        T t = eles[i];
        for (int j = i; j <eles.length-1 ; j++) {
            eles[j] = eles[j+1];
        }
        N--;
        //删除元素后，判断该线性表长度是否小于数组容器的4分之一，小于则将数组容器的长度减半，减少空间浪费
        if(N <= eles.length/4){
            eles = reSize(eles.length/2);
        }
        return t;
    }

    //查找t元素第一次出现的第一个位置
    public int indexof(T t){
        for (int i = 0; i <eles.length ; i++) {
            if(t.equals(eles[i])){
                return i;
            }
        }
        return -1;
    }

    //在元素插入与删除时进行扩容或者缩容的方法
    public T[] reSize(int newsize){
        T[] t = (T[]) new Object[newsize];
        for (int i = 0; i <eles.length ; i++) {
            t[i] = eles[i];
        }
        System.out.println("public T[] reSize");
        return  t;
    }

    @Override
    public String toString() {
        return "SequenceList{" +
                "N=" + N +
                ", eles=" + Arrays.toString(eles) +
                '}';
    }
}

